/*
 * @lc app=leetcode.cn id=287 lang=javascript
 *
 * [287] 寻找重复数
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    let hash=new Set()
    for(let i=0;i<nums.length;i++){
        if(hash.has(nums[i])){
            return nums[i]
        }else{
            hash.add(nums[i])
        }
    }    
};


// @lc code=end

const findDuplicate = (nums) => {
    let lo = 1;
    let hi = nums.length - 1; //题目注明了：nums.length == n + 1
    while (lo < hi) {
        const mid = (lo + hi) >>> 1;  // 求中间索引
        let count = 0;
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] <= mid) {
                count++;
            }
        }
        if (count > mid) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    return lo;
};//值域二分